1. Field of the Invention
The present invention relates to a route selection system, and more specifically, it relates to a system for automatically selecting the optimum route between a starting place and a destination which are designated on a map.
2. Background of the Invention
Navigation systems for guiding cars are rapidly coming into wide use following the development of electronic techniques. Some conventional navigation systems comprise a route selection system for automatically selecting the optimum route from a starting place to a destination, such as the shortest route or the minimum time route, for example.
In relation to the conventional route selection system, Japanese Patent Laying-Open No. 59-105113 (1984), for example, discloses an automatic car navigation method as a method of obtaining the optimum route for guiding a car. This method is adapted to obtain the optimum route between a starting place and a destination from data expressing a network of roads by a Dijkstra method, which is one of optimum route deciding methods, or the like. The theory of the Dijkstra method is described in "Data Structure and Algorithm" written by Alfred V. Aho and translated by Yoshio Ono, Kabushiki Kaisha Baifu-Kan, published in 1990, pp. 179 to 183, for example.
On the other hand, Japanese Patent Laying-Open No. 2-56591 (1990), for example, discloses a route search method which executes a search through map data having a hierarchical structure for obtaining the optimum route, in order to reduce the calculation time.
In the aforementioned search for the optimum route between two arbitrary spots on the network, however, the routing time is disadvantageously increased as the number of crossings and roads included in the network are increased. Consequently, the user's waiting time is increased to 2 to 3 minutes, leading to inconvenience. Further, generally provided road system data are so detailed and enormous in quantity (several gigabytes) that it is difficult to obtain the route directly from such data on an on-vehicle unit.
While it may be possible to select the route through thinned rough road system data such as those excluding general roads other than national roads and highways as described in Japanese Patent Laying-Open No. 2-56591 (1990), for example, detailedness of the obtained route is reduced as compared with the case of employing detailed road system data, leading to such inconvenience that roads to be passed cannot be clearly recognized except the national roads and highways, for example.
In the conventional method, further, the obtained optimum route cannot be changed even if the same includes a road to be avoided for the user's own reasons.